For each element A[i] of array A, find the closest j such that A[j] > A[i]
Posted
by SamH
on Stack Overflow
See other posts from Stack Overflow
or by SamH
Published on 2010-03-31T20:03:10Z
Indexed on
2010/05/27
6:31 UTC
Read the original article
Hit count: 164
distance
|euclidean-distance
Hi everyone.
Given : An array A[1..n] of real numbers.
Goal : An array D[1..n] such that
D[i] = min{ distance(i,j) : A[j] > A[i] }
or some default value (like 0) when there is no higher-valued element. I would really like to use Euclidean distance here.
Example :
A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]
Is there any way to beat the obvious O(n^2) solution? The only progress I've made so far is that D[i] = 1 whenever A[i] is not a local maxima. I've been thinking a lot and have come up with NOTHING. I hope to eventually extend this to 2D (so A and D are matrices).
© Stack Overflow or respective owner
